Exercise 12 (Homework 2).
(regular languages,
polynomial time,
membership problem)
Membership in a regular language is decidable in polynomial time
Consider the following decision problem:
\mathtt{Membership_{Reg}}: \text{ given an input $x\in \{0,1\}^*$ and a DFA $A$, determine whether } x\in L(A).
Show that \mathtt{Membership_{Reg}} can be decided in polynomial time w.r.t. |x| and the size of A.